Depth 4 Lower Bounds, Determinantal Complexity : A Unified Approach

Link to the article

Authors

Suryajith Chillara and Partha Mukhopadhyay

Publisher Information

Abstract

Tavenas has recently proved that any $n^{O(1)}$-variate and degree $n$ polynomial in $VP$ can be computed by a depth 4 $\Sigma\Pi\Sigma\Pi$ circuit of size $2^{O(\sqrt{n}\log n)}$ (see Tavenas (2013)). So, to prove $VP\neq VNP$ it is sufficient to show that an explicit polynomial in $VNP$ of degree $n$ requires $2^{\omega(\sqrt{n}\log n)}$ size depth 4 circuits. Soon after Tavenas' result, for two different explicit polynomials, depth 4 circuit size lower bounds of $2^{\Omega(\sqrt{n}\log n)}$ have been proved (see Kayal-Saha-Saptharishi (2013) and Fournier-Limaye-Malod-Srinivasan (2013)). In particular, using combinatorial design Kayal et al. construct an explicit polynomial in $VNP$ that requires depth 4 circuits of size $2^{\Omega(\sqrt{n}\log n)}$ and Fournier et al. show that the iterated matrix multiplication polynomial (which is in $VP$) also requires $2^{\Omega(\sqrt{n}\log n)}$ size depth 4 circuits.

In this paper, we identify a simple combinatorial property such that any polynomial $f$ that satisfies this property would achieve a similar depth 4 circuit size lower bound. In particular, it does not matter whether $f$ is in $VP$ or in $VNP$. As a result, we get a simple unified lower bound analysis for the above mentioned polynomials.

Another goal of this paper is to compare our current knowledge of the depth 4 circuit size lower bounds and the determinantal complexity lower bounds. Currently the best known determinantal complexity lower bound is $\Omega(n^2)$ for Permanent of a $n\times n$ matrix (which is a $n^2$-variate and degree $n$ polynomial) (due to Cai, Chen and Li (2008)). We prove that the determinantal complexity of the iterated matrix multiplication polynomial is $\Omega(dn)$ where $d$ is the number of matrices and $n$ is the dimension of the matrices. So for $d=n$, we get that the iterated matrix multiplication polynomial achieves the current best known lower bounds in both fronts: depth 4 circuit size and determinantal complexity. Our result also settles the determinantal complexity of the iterated matrix multiplication polynomial to $\Theta(dn)$.

To the best of our knowledge, a $\Theta(n)$ bound for the determinantal complexity for the iterated matrix multiplication polynomial was known only for any constant $d>1$ (cf. Jansen (2011)).